/*
 * @lc app=leetcode.cn id=321 lang=javascript
 *
 * [321] 拼接最大数
 */

// @lc code=start
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[]}
 */
var maxNumber = function (nums1, nums2, k) {
  let result = [];
  for (let i = 0; i <= k; i++) {
    if (i <= nums1.length && k - i <= nums2.length) {
      const a = pickMax(nums1, i);
      const b = pickMax(nums2, k - i);
      const res = merge(a, b);
      result = result > res ? result : res;
    }
  }

  return result;

  function pickMax(nums, k) {
    let discards = nums.length - k;
    const stack = [];

    for (let n of nums) {
      while (stack.length && discards && stack[stack.length - 1] < n) {
        stack.pop();
        discards--;
      }
      stack.push(n);
    }
    return [...stack.splice(0, k)];
  }

  function merge(a, b) {
    const result = [];
    while (a.length || b.length) {
      let bigger = a > b ? a : b;
      result.push(bigger[0]);
      bigger.shift();
    }
    return result;
  }
};
// @lc code=end
